class Solution:
    """
    887. 鸡蛋掉落
    https://leetcode-cn.com/problems/super-egg-drop/
    @date 2021年2月17日15:49:06
    @author mizzle rain
    """
    def superEggDrop(self, K: int, N: int) -> int:
        memo = dict()
        def dp(k, n):
            if k == 1:
                return n
            if n == 0:
                return 0
            if (k, n) in memo:
                return memo[(k, n)]
            res = float('INF')
            left, right = 1, n
            while left <= right:
                mid = left + right >> 1
                a, b = dp(k - 1, mid - 1), dp(k, n - mid)
                if a > b:
                    right = mid - 1
                    res = min(a + 1, res)
                else:
                    left = mid + 1
                    res = min(b + 1, res)
            memo[(k, n)] = res
            return res
        return dp(K, N)